/********************************************************************************************************************************
 * 
 * 循环链表
 * 
 ********************************************************************************************************************************/
#include <cstdlib>
/********************************************************************************************************************************
 * 
 * 循环单链表
 * 
 * */

/**
 * 单链表中结点类型的描述
 * */
typedef int ElemType;                        //定义元素的类型

typedef struct LNode{                       //定义单链表的结点类型
    ElemType data;                          //数据域
    struct LNode *next;                     //指针域
}LNode,*LinkList;

/**
 * 初始化一个循环单链表
 * */
bool InitList(LinkList &L){
    L = (LNode *)malloc(sizeof(LNode));
    if(L == NULL)
        return false;
    L->next = L;                            //头结点指针指向头结点
    return true;
}

/**
 * 判断一个循环单链表是否为空
 * */
bool Empty(LinkList L){
    return (L->next == L);
}

/**
 * 判断结点p是否时循环单链表的表尾结点
 * */
bool isTail(LinkList L, LNode *p){
    return (p->next == L);
}

/********************************************************************************************************************************
 * 
 * 循环双链表
 * 
 * */

/**
 * 双链表中结点类型的描述
 * 
 * */
typedef struct DNode{                       //定义双链表结点类型
    ElemType data;                          //数据域
    struct DNode *prior, *next;             //前驱和后继的指针
}DNode, *DLinkList;

/**
 * 初始化循环双链表
 * 
 * */
bool InitDLinkList(DLinkList &L){
    L = (DNode *)malloc(sizeof(DNode));     //分配一个头结点
    if(L == NULL)                           //内存分配失败
        return false;
    L->prior = L;                        //头结点的prior指向L(当不为空时指向尾结点)
    L->next = L;                         //头结点next指向L

    return true;
}

/**
 * 判断循环双链表是否为空
 * */
bool Empty(DLinkList L){
    return (L->next == L);
}

/**
 * 判断结点p是否时循环双链表的表尾结点
 * */
bool isTail(LinkList L, LNode *p){
    return (p->next == L);
}

/**
 * 循环双链表 ：
 * 
 * 在p结点之后插入s结点
 * */
bool InsertNextDNode(DNode *p, DNode *s){
    s->next = p->next;
    p->next->prior = s;
    s->prior = p;
    p->next = s;
    
    return true;
}

/**
 * 双链表的删除操作
 * 
 * 删除双链表中结点 *p 的后继结点 *q
 * 
 * */

bool ListDelete(DNode *p){
    DNode *q = p->next;
    p->next = q->next;
    q->next->prior = p;
    free(q);                            //释放结点空间

    return true;
}